

\newsavebox{\firstlisting}
% removed from listing
% City."CITY" AS city,
% Customer."AGE" AS age,
\begin{lrbox}{\firstlisting}

\begin{lstlisting}[basicstyle=\ttfamily\footnotesize]
SELECT
 sum(Invoice_Line."DAYS"
  * Invoice_Line."NB_GUESTS"
  * Service."PRICE") AS revenue,
 Customer."LAST_NAME" AS customer
FROM City
INNER JOIN Customer
 ON (City."CITY_ID"=Customer."CITY_ID")
INNER JOIN Sales
 ON (Sales."CUST_ID"=Customer."CUST_ID")
INNER JOIN Invoice_Line
 ON (Invoice_Line."INV_ID"=Sales."INV_ID")
INNER JOIN Service
 ON (Invoice_Line."SERVICE_ID"=Service."SERVICE_ID")
WHERE
 city = 'Palo Alto' AND
 age >= 20 AND
 age <= 30
GROUP BY
 customer
ORDER BY revenue
LIMIT 5
\end{lstlisting}
\end{lrbox}
\begin{figure*}[!ht]
\vspace{-2cm}
\centering
 \subfloat[ A user's question and derived semantic units (comparable to a parse
tree in natural language processing).
Successive tokens that satisfy some constraints (e.g. linguistics pattern or
dictionary matches) are marked with dotted boxes. Inferred semantics
are drawn with solid rectangles. These semantic units of recognized
entities form parts of potential structured queries that might fullfill the
users information need. In addition, the system has to propose a measure for
`?1' to compute a valid multi-dimensional query.] {\label{fig:running-example}
\begin{minipage}[c][1\width]{0.5\textwidth}
\centering
\includegraphics[clip=true,trim = 8cm 11cm 9.5cm
3cm,width=1.00\linewidth]{img/running-example.pdf}
\vspace{-1.3cm}
\end{minipage}}
\subfloat[Example SQL query that was generated from the user's question in
figure~\ref{fig:running-example}.
Natural language patterns, constraints given by the data and metadata of the
data warehouse (see figure~\ref{fig:data-schema}) have been applied to infer
query semantics.
This was mapped to a logical, multi-dimensional query, which in turn was
translated to SQL. Note, that the `revenue' represents a proposed measure,
depicted as `?1' in figure~\ref{fig:running-example}.
The computation of the measure `revenue' and the join paths are configured in
the metadata of the warehouse.]{\label{lst:structured-query-1}
\begin{minipage}[c][1\width]{ 0.5\textwidth}
\centering
{\usebox{\firstlisting}}
\vspace{-1.8cm}
\end{minipage}}
\vspace{-.cm}
\caption{Translating a user's question into a structured query.}
\label{fig:translation-process}
\vspace{-.8cm}
\end{figure*}


In the last decades data warehouses became an important information source for
decision making and controlling. A lot of progress has been made to support
casual end-users by allowing interactive navigation inside complex reports or
dashboards (e.g. by interactive filtering or calling OLAP-operations such as
drill-down in a user-friendly way). In addition there has been a lot of effort
in making reports or dashboards searchable.
%
However, most casual users still have to rely on pre-canned reports that are
provided by the IT-department of a company because todays' Business Intelligence 
(BI) self-service tools still require a lot of technical insights such as 
an understanding of the data warehouse schema. 
This is especially cumbersome because data warehouses
grew dramatically in size and complexity. A popular use-case for BI is for
instance the segmentation of customers to plan marketing campaigns (e.g. to
derive the most valuable, middle-aged customers in a certain region). It is not
unusual that business users who plan a campaign have to cope with hundreds of
key performance indicators (KPIs) and attributes, which they have to combine in
an ad-hoc fashion to cluster their customer base. A keyword or even natural
language-based interface to formulate their information need would ease this
task a lot. 
%
% a lot as users are more comfortable to use unstructured query interfaces
%compared to very structured ones~\cite{Hearst:2011:NSU:2018396.2018414}.
%
This can be underlined with the recent success of question answering systems,
such as WolframAlpha\footnote{See \url{http://www.wolfram.com/mathematica/}.},
especially in conjunction with speech-to-text technologies like
Siri\footnote{\url{http://www.apple.com/iphone/features/#siri}.} and the
huge efforts in the database community to enable keyword-based search in
databases (e.g. 
\cite{He:2007:BRK:1247480.1247516,
Tata:2008:SDM:1376616.1376705,
Tran:2007:OIK:1785162.1785201}).

However, the keyword based approaches developed so far lack many important
features to fully enable a question-driven data exploration by end-users,
where the consideration of range queries, the support to include
application-specific vocabulary (e.g. ``middle-aged'') or leveraging of the
users' context (e.g. ``customers in my region'') are only the most obvious
ones. Note that the problem is not only to extract semantics from a user's
question (e.g. from a range phrase such as ``between 1999 and 2012''), which
is supported by our framework as well. The more important problem is to relate
findings detected in a user's question to formulate a well-defined structured
query.
%
The framework presented in this paper supports the whole process of defining
and executing a domain or application-specific Question Answering system. We
provide a basic infrastructure for entity recognition, which we briefly introduce 
in section~\ref{information-extraction}. The main innovation, i.e. 
the declarative description of constraints on the user input and background knowledge; 
definition of variables to be used in the structured query  
and the mapping of this variables into arbitrary 
structured queries will be discussed in
section~\ref{sec:structural-constraints} and section~\ref{sec:mapping}. In 
section~\ref{sec:scoring}, we elaborate the ranking of computed structured 
queries. The experimental evaluation of our framework can be found in section 
\ref{sec:evaluation} and the related work in section~\ref{sec:state-of-the-art}. 
However, before going into the details of our approach, we like to introduce the
problem in section~\ref{sec:problem} and give an overview on the system and
the data structures that we leverage in section~\ref{system-overview}.

